package top100

import (
	"fmt"
	"math"
)

// 这题太典型了，很多题都是和这题类似或思路一致
/*
已知 132 模式， nums[i] < nums[k] < nums[j]， 从前到后，顺序遍历每一元素
1. 能满足是 k 的，就 "可能" 满足它也是个 j
2. 所以我们需要先确定一个位置是否是 k
        这个很好做，维护当前位置之前最小的 i 值（numI）,只要大于这个就可以是 k
3. 如果当前位置是 k， 那么它可能是 j： 维护一个 "有条件的递减栈"！
        （1）如果栈空，直接将当前k压入栈中（它可能是j）
        （2）如果栈非空，那当前的 k对应的 nums[k] 如果小于栈顶的 k，就可能满足132：
                如果 它们对应的 i 值是相等的，一定满足 132 ,i j k 顺序对。return true。栈顶的k能当做 j
                不相等，一定有 栈顶的 i 值 大于 当前k的i值， 比较当前 k值 和栈顶的k 对应的i值
                    如果 k > 栈顶的i 值，满足 132 ，return true
                    否则，说明 当前的位置是 [栈顶, 当前k的i值, 当前k] 变成了这个样子，j i k 了不满足。
                    此时 满足递减栈的条件： 当前k小于栈顶元素， 且 i值不相等。进栈。
        （3）如果栈非空，且当前k 大于 栈顶元素
            那么栈顶的 i 一定等于 或者小于 当前k的i，循环判断，依次剔除掉栈顶的值，最后当前k入栈
            因为进栈的 k越大，后续才更容易出现比它小的，当前k，才能以变为 j
        （4）最后没有结果，就返回 false了
*/
func find132pattern(nums []int) bool {
	n := len(nums)
	// 定义栈，[值, numsI] 栈中元素表示的是，当前的元素 和 对应的nums[i]值
	stack := make([][2]int, 0)
	// 定义当前位置最小 nums[i]
	numI := nums[0]
	// 循环开始找满足条件的 nums[k], 或nums[j],因为下标1-n, 满足j 和 k的位置
	for k := 1; k < n; k++ {
		numI = min(numI, nums[k-1])
		// 1. 当前元素小于 numI 不能作为 k，直接退出
		if nums[k] < numI {
			continue
		}

		// 4. 如果大于, pop栈顶元素: 这里使用大于等于：[40,50,25,35,15,35,20]
		// 这个例子中的 35， 后买的35满足条件吗，但是如果没有等于的话，不会删除掉栈中前面的35，就得不到正确结果
		// 这个例子，[80,84,70,80,60,70,50,60,82,85]， 最终后面的82 要淘汰删除多组栈顶，才能和 84 进行比较，需要用 for。
		// (84, 80) (80, 70) (70, 60) (60, 50), (82, 50)
		for len(stack) > 0 && nums[k] >= stack[len(stack)-1][0] {
			stack = stack[:len(stack)-1]
		}
		// 3. nums[k] 小于当前的栈顶元素，可能满足 132
		if len(stack) > 0 && nums[k] < stack[len(stack)-1][0] {
			// nums[k] 小于栈顶， 大于栈顶的 numI，满足
			if nums[k] > stack[len(stack)-1][1] {
				fmt.Println(stack[len(stack)-1][1], stack[len(stack)-1][0], nums[k])
				return true
			}
		}
		// 其他情况，全部进栈
		stack = append(stack, [2]int{nums[k], numI})
	}
	return false
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}
